package top.lcm668.study.oj.base.sortmethods.mergesort;

/**
 * @author: Coder-Lcm
 * @date: 2021/10/5 8:26
 * 自顶向下的归并排序算法:
 *  将⼀个⼤数组分成两个小数组去求解。
 * 因为每次都将问题对半分成两个⼦问题，这种对半分的算法复杂度⼀般为 O(NlogN)。
 */
public class Up2DownMergeSort<T extends Comparable<T>> extends BaseMergeSort<T> {

    @Override
    protected void sort(T[] arr, boolean isAsc) {
        helperArr = (T[]) new Comparable[arr.length];
        sort(arr, 0, arr.length - 1);
    }

    private void sort(T[] arr, int l, int h) {
        if (h <= l) {
            return;
        }
        // 取中点，这个写法主要是防止 (h+l) / 2 发生溢出
        int mid = l + (h - l) /2;
        sort(arr, l, mid);
        sort(arr, mid + 1, h);
        merge(arr, l, mid, h);
    }
}
